//#include<stdio.h>
//
//int main()
//{
//    int n=0;
//    scanf("%d",&n);
//    printf("%d",(n/100 % 10 *10000)+(n*10)+(n%10));
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int f=0;
//    scanf("%d",&f);
//    float c =5*(f-32)/9.0;
//    printf("%.1f",c);
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int n=0;
//    scanf("%d",&n);
//    int ji=2;
//    int i=0;
//    for (i=1;i<n;i++)
//    {
//        ji=ji*2;
//    }
//    printf("2^%d=%d",n,ji);
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int r=0;
//    scanf("%d",&r);
//    double c=2*3.14159*r;
//    double s=3.14159*r*r;
//    printf("%.2lf %.2lf",c,s);
//    return 0;  
//}
//#include<stdio.h>
//
//int main()
//{
//    float x=0;
//    scanf("%f",&x);
//    float jb=1+x;
//    float tb=1-x;
//    int i=0;
//    for (i=1;i<365;i++){
//        jb=jb*(1+x);
//    }
//    for (i=1;i<365;i++){
//        tb=tb*(1-x);
//    }
//    printf("%.8f\n%.8f",jb,tb);
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    double x=0;
//    scanf("%lf",&x);
//    double jb=pow(1+x,365);
//    double tb=pow(1-x,365);
//    printf("%.8lf\n",jb);
//    printf("%.8lf",tb);
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
////    double A;
////    double B;
////    scanf("%lf %lf",&A,&B);
////    double C=A;
////    A=B;
////    B=C;
////    printf("%lf,%lf",A,B);
//	printf("%f",23.45 % 1);
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int time;
//    int minute;
//    scanf("%d %d",&time,&minute);
//    int t=(time/100*60+(time % 100+minute))/60;
//    int m=(time/100*60+(time % 100+minute))% 60;
//    printf("%03d",t*100+m);
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    int T=0;
//    scanf("%d",&T);
//    int i=0;
//    for (i=0;i<T;i++){
//        int A,B,C;
//        scanf("%d %d %d",&A,&B,&C);
//        int ji=pow(A,B);
//        printf("%d\n",ji % C);
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    int T=0;
//    scanf("%d",&T);
//    int i=0;
//    for (i=0;i<T;i++){
//        int A,B,C,result;
//        result=1;
//        scanf("%d %d %d",&A,&B,&C);
//        int j=0;
//        for (j=0;j<B;j++){
//            result=(result*A )% C;
//        }
//        printf("%d\n",result);
//    }
//    return 0;
//}
#include<stdio.h>
#include<math.h>
int main()
{
    int T=0;
    scanf("%d",&T);
    int i=0;
    for (i=0;i<T;i++){
        int A=0;
        int B=0;
        int C=0;
        scanf("%d %d %d",&A,&B,&C);
        if (C != 0){
            int jg=pow(A,B);
            jg=jg % C;
            printf("%d\n",jg);
        }
    }
    return 0;
}
